// https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/

// 算法思路总结：
// 1. 使用贪心策略处理数组减半问题
// 2. 维护最大堆存储当前数组元素，优先减少最大元素
// 3. 每次取出最大元素减半，累加减少的总和
// 4. 当减少的总和达到原数组总和一半时停止
// 5. 时间复杂度：O(nlogn)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>

class Solution 
{
public:
    int halveArray(vector<int>& nums) 
    {
        int m = nums.size();

        priority_queue<double> maxHeap(nums.begin(), nums.end());
        double sum = accumulate(nums.begin(), nums.end(), 0.0);
        double cur = 0.0;
        int count = 0;

        while (cur < sum / 2)
        {
            double top = maxHeap.top();
            maxHeap.pop();
            cur += top / 2;
            maxHeap.push(top / 2);
            count++;
        }

        return count;
    }
};

int main()
{
    vector<int> v1 = {5,19,8,1}, v2 = {3,8,20};
    Solution sol;

    cout << sol.halveArray(v1) << endl;
    cout << sol.halveArray(v2) << endl;

    return 0;
}